package org.leetcode.easy.leetcode69;

public class Solution2 {

    public static void main(String[] args) {
        int num = mySqrt(2147395599);
        System.out.println(num);
    }

    public static int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            //int mid =(left+right)>>>1;
            long num = (long) mid * mid;
            long biggerNum = (long) (mid + 1) * (mid + 1);

            if (num <= x && biggerNum > x) {
                return mid;
            } else if (num > x) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }


}
